package code.starivan.leetcode;

import code.starivan.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Ivan on 2015/10/21.
 */

/*
Given a binary tree, return the preorder traversal of its nodes' values.

        For example:
        Given binary tree {1,#,2,3},
        1
        \
        2
        /
        3
        return [1,2,3].

        Note: Recursive solution is trivial, could you do it iteratively?
*/

public class N144_BinaryTreePreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> ret=new ArrayList<>();
        TreeNode cur1=root;
        TreeNode cur2=null;
        while (cur1!=null){
            cur2=cur1.left;
            if(cur2!=null){
                while (cur2.right!=null&&cur2.right!=cur1){
                    cur2=cur2.right;
                }
                if(cur2.right==null){
                    ret.add(cur1.val);
                    cur2.right=cur1;
                    cur1=cur1.left;
                    continue;
                }else{
                    cur2.right=null;
                }
            }else{
                ret.add(cur1.val);
            }

            cur1=cur1.right;
        }

        return ret;
    }
}
